package com.ming.learn.from.carl.hash;

/*
第242题. 有效的字母异位词
 */
public class Of20201222LeetCode242 {
    /*
    给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
     */
    /*
    暴力解法
    两层for循环
    时间复杂度 O(n^2)
    代码略
     */

    /*
    「数组其实就是一个简单哈希表」
    「因为字符a到字符z的ASCII是26个连续的数值，所以字符a映射为下表0，相应的字符z映射为下表25。」
    「只需要将 s[i] - ‘a’ 所在的元素做+1 操作即可，并不需要记住字符a的ASCII，只要求出一个相对数值就可以了。」
    「record数组如果有的元素不为零0，说明字符串s和t一定是谁多了字符或者谁少了字符，return false。」
     */
    /*
    时间复杂度为O(n)
    空间上因为定义是的一个常量大小的辅助数组，所以空间复杂度为O(1)。
     */
    static boolean isAnagram(String s, String t) {
        if (s.length()!=t.length())
            return false;
        int[] record = new int[26];
        for (int i = 0; i < s.length(); i++) {
            // 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了
            record[s.charAt(i)-'a']++;
        }
        for (int i = 0; i < t.length(); i++) {
            record[t.charAt(i)-'a']--;
        }
        for (int i = 0; i < 26; i++) {
            if (record[i]!=0)
                // record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。
                return false;
        }
        // record数组所有元素都为零0，说明字符串s和t是字母异位词
        return true;
    }

    public static void main(String[] args) {
        System.out.println(isAnagram("qwertyuiop", "poiuytrewq"));
    }
}
